/*
  Name: 图的邻接矩阵存储结构 
  Copyright: BTC 2004
  Author: Zhuang Bo
  Date: 2004
  Description: 
*/

#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED

#include <stdio.h>
#include "ds.h"

///////////////////////////////////////////////////////////
//图的邻接矩阵表示
#define MAX_VERTEX_NUM 20 //最大顶点数
#define VexType char //顶点类型
#define ArcType int
#define INFINITY INT_MAX  //无穷大 
typedef struct {
    VexType  vexs[MAX_VERTEX_NUM]; //顶点向量 
    ArcType  arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 
    int      vexnum;   //顶点个数
} MGraph;

///////////////////////////////////////////////////////////
//图的基本操作声明 

//输入顶点和弧的信息，建立图
Status CreateGraph(MGraph &G); 
//销毁图的结构
Status DestroyGraph(MGraph &G);

//取顶点
VexType GetVex(MGraph G, int v);
//更新顶点信息 
Status PutVex(MGraph &G, int v, VexType val);
//插入弧(v,w)
Status InsertArc(MGraph &G, int v, int w, ArcType arc);
//删除弧(v,w)
Status DeleteArc(MGraph &G, int v, int w);
//插入顶点v
Status InsertVex(MGraph &G, VexType val);
//删除顶点v
Status DeleteVex(MGraph &G, int v);

//图G中顶点v的第一个邻接点
int FirstAdjVex(MGraph G, int v);
//图G中顶点v在w之后的下一个邻接点
int NextAdjVex(MGraph G, int v, int w);

//深度优先遍历图
Status DFSTraverse(MGraph G, int v, Status(*Visit)(VexType));
//广度优先遍历图 
Status BFSTraverse(MGraph G, int v, Status(*Visit)(VexType));

//打印邻接矩阵(调试用)
void PrintAdjMatrix(MGraph G);


///////////////////////////////////////////////////////////
//基本操作的实现

//输入顶点和弧的信息，建立图
Status CreateGraph(MGraph &G)
{
    //-------------------------------------
    // TODO (#1#): 先输入顶点个数和顶点数据,然后输入弧，建立图 
    return ERROR;
    //-------------------------------------
}

//销毁图的结构
Status DestroyGraph(MGraph &G)
{
    return OK;//什么也不做
} 

//取顶点
Status GetVex(MGraph G, int v, VexType &val)
{
    if(v<0||v>=G.vexnum) return ERROR;
    val = G.vexs[v];
    return OK;
}

//更新顶点信息 
Status PutVex(MGraph &G, int v, VexType val)
{
    if(v<0||v>=G.vexnum) return ERROR;
    G.vexs[v] = val;
    return OK;
}

//插入弧(v,w)
Status InsertArc(MGraph &G, int v, int w, ArcType arc)
{
    if(v<0||v>=G.vexnum||w<0||w>=G.vexnum) return ERROR;
    G.arcs[v][w] = arc;
    return OK;
}

//删除弧(v,w)
Status DeleteArc(MGraph &G, int v, int w)
{
    if(v<0||v>=G.vexnum||w<0||w>=G.vexnum) return ERROR;
    G.arcs[v][w] = 0; //删除弧 
    return OK;
}

//插入顶点v
Status InsertVex(MGraph &G, VexType val)
{
    //-------------------------------------
    // TODO (#1#): 插入顶点v,注意对邻接矩阵的影响
    return ERROR;
    //-------------------------------------
}

//删除顶点v
Status DeleteVex(MGraph &G, int v)
{
    //-------------------------------------
    // TODO (#1#): 删除顶点v,注意对邻接矩阵的修改
    return ERROR;
    //-------------------------------------
}

//图G中顶点v的第一个邻接点，不存在时返回 -1 
int FirstAdjVex(MGraph G, int v)
{
    //-------------------------------------
    // TODO (#1#): 返回顶点v的第一个邻接点
    return -1;
    //-------------------------------------
}

//图G中顶点v在w之后的下一个邻接点，不存在时返回 -1
int NextAdjVex(MGraph G, int v, int w)
{
    //-------------------------------------
    // TODO (#1#): 返回顶点v在w之后的下一个邻接点
    return -1;
    //-------------------------------------
}

//深度优先遍历图
Status DFSTraverse(MGraph G, int v, Status(*Visit)(VexType))
{
    //-------------------------------------
    // TODO (#1#): 从v出发，深度优先遍历图
    return -1;
    //-------------------------------------
}

//广度优先遍历图 
Status BFSTraverse(MGraph G, int v, Status(*Visit)(VexType))
{
    //-------------------------------------
    // TODO (#1#): 从v出发，广度优先遍历图
    return -1;
    //-------------------------------------
}

//打印邻接矩阵
void PrintAdjMatrix(MGraph G) 
{
    int i,j;
    for(i=0; i<G.vexnum; i++) {
        write(G.vexs[i]);
        for(j=0; j<G.vexnum; j++)
            printf("%5d", G.arcs[i][j]);
        printf("\n");
    }
}

#endif //GRAPH_H_INCLUDED

